﻿// 1-14.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<vector>
int sqr(int a) { return a * a; }  //平方运算

//计算2^n
//递归版
//复杂度 logn
int powerA(int n) {
    if (n == 0) return 1;
    return (n & 1) ? sqr(powerA(n >> 1)) << 1 : sqr(powerA(n >> 1));  //选择性递归
}
//计算2^n
//迭代版
//复杂度logn
//思路，以迭代重现递归的思路，
//从前到后，关键在于，每一步的分岔路口如何选择，我的想法是，先把递归的没一步都记下来，然后迭代重现
int powerB(int n) {
    std::vector<int> vec;
    int onebase = 1;
    while (0 < n) { //本身不会大过本身，故本身多少，则意味多少停止
        if (n & 1) vec.insert(vec.begin(),1);
        else
        {
            vec.insert(vec.begin(), 0);
        }
        n >>= 1;
    }
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i] & 1) {
            onebase = sqr(onebase) << 1;
        }
        else
        {
            onebase = sqr(onebase);
        }
    }
    return onebase;
}

//计算2^n
//迭代版
//复杂度logn
//思路：经由递归思路所得的数学规律，以此数学规律为核心，写出2^n算法
int powerC(int n) {
    int pow = 1; //2^0是为1，亦是整个数学公式中的乘法之底，以底向上收拢所有比特位的权重
    int p = 2;  //权重小单位，下一权重计算方式为：上一权重之平方
    while (0 < n) {
        if (n & 1) pow *= p;  //观察课本上整理的例子，不难看出，唯有比特位为1时，其比特位置上所占的权重，才对最终结果有所贡献
        n >>= 1;  //消去一个比特位
        p *= p;  //顺便得到下一比特位之权重
    }
    return pow;
}

//计算a^n
//迭代版
//复杂度logn
//思路：powerC的推广版
int powerD(int a, int n) {//a为底数，n为指数（n>=0）,至于你a的正负，对我无影响（重点在，它们两各自在最终乘法表达式中的位置）
    int pow = 1;  //a^0为1，同样是整个乘法结果单位中的底
    int p = a;  //权重最小单位此时为a，下一权重计算方法：上一权重的平反
    while (0 < n)
    {
        if (n & 1)pow *= p;
        n >>= 1;  //指数缩半
        p *= p;  //下一比特位对应权重
    }
    return pow;
}
int main()
{
    std::cout << "开始\n";
    int a = powerA(16);
    int b = powerB(16);
    int c = powerC(16);
    int d = powerD(2,16);
    std::cout << a << "\n";
    std::cout << b << "\n";
    std::cout << c << "\n";
    std::cout << d << "\n";
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
